package algorithm.leetcode.I201to400;

import algorithm.leetcode.TreeNode;

import java.util.HashMap;
import java.util.Map;

public class Q337 {

    // 方法一:最慢,暴力递归,最好理解
    // 4 个孙子偷的钱 + 爷爷的钱 VS 两个儿子偷的钱 哪个组合钱多，就当做当前节点能偷的最大钱数。这就是动态规划里面的最优子结构
    public int rob(TreeNode root) {
        if (root == null) return 0;

        // 计算第一种情况时候要判断下子辈是否为null
        int twoGrandGen = root.val + (root.left == null ? 0 : rob(root.left.left)+rob(root.left.right)) + (root.right == null ? 0 : rob(root.right.left)+rob(root.right.right));
        int onlySonGen = rob(root.left) + rob(root.right);
        return Math.max(twoGrandGen, onlySonGen);
    }


    // 记忆化,减少重复计算
    public int rob2(TreeNode root) {
        if (root == null) return 0;
        return rob2Helper(root, new HashMap<>());
    }

    private int rob2Helper(TreeNode node, Map<TreeNode, Integer> memo) {
        if (node == null) return 0;
        if (memo.containsKey(node)) return memo.get(node);

        int twoGrandGen = node.val;
        if (node.left != null) twoGrandGen += rob2Helper(node.left.left, memo) + rob2Helper(node.left.right, memo);
        if (node.right != null) twoGrandGen += rob2Helper(node.right.left, memo) + rob2Helper(node.right.right, memo);
        int onlySonGen = rob2Helper(node.left, memo) + rob2Helper(node.right, memo);
        int maxVal = Math.max(twoGrandGen, onlySonGen);
        memo.put(node, maxVal);
        return maxVal;
    }

}
